home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / rbtree.jav < prev    next >
Text File  |  1995-12-14  |  9KB  |  342 lines
  1. /*
  2.   File: RBTree.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  * RedBlack trees.
  23.  * @author Doug Lea
  24.  * @version 0.93
  25.  *
  26.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  27. **/
  28.  
  29. public class RBTree extends    UpdatableBagImpl
  30.                     implements UpdatableBag, 
  31.                                ElementSortedCollection {
  32.  
  33. // instance variables
  34.  
  35. /**
  36.  * The root of the tree. Null if empty.
  37. **/
  38.  
  39.   protected RBCell tree_;
  40.  
  41. /**
  42.  * The comparator to use for ordering.
  43. **/
  44.   protected Comparator cmp_;
  45.  
  46. // constructors
  47.  
  48. /**
  49.  * Make an empty tree.
  50.  * Initialize to use DefaultComparator for ordering
  51. **/
  52.   public RBTree() { this(null, null, null, 0); }
  53.  
  54. /**
  55.  * Make an empty tree, using the supplied element screener.
  56.  * Initialize to use DefaultComparator for ordering
  57. **/
  58.  
  59.   public RBTree(Predicate s) { this(s, null, null, 0); }
  60.  
  61. /**
  62.  * Make an empty tree, using the supplied element comparator for ordering.
  63. **/
  64.   public RBTree(Comparator c) { this(null, c, null, 0); }
  65.  
  66. /**
  67.  * Make an empty tree, using the supplied element screener and comparator
  68. **/
  69.   public RBTree(Predicate s, Comparator c) { this(s, c, null, 0); }
  70.  
  71. /**
  72.  * Special version of constructor needed by clone()
  73. **/
  74.  
  75.   protected RBTree(Predicate s, Comparator cmp, RBCell t, int n) { 
  76.     super(s); 
  77.     count_ = n;
  78.     tree_ = t;
  79.     if (cmp != null) cmp_ = cmp;
  80.     else cmp_ = new DefaultComparator();
  81.   }
  82.  
  83. /**
  84.  * Make an indepenent copy of the tree. Does not clone elements.
  85. **/
  86.   protected Object clone() throws CloneNotSupportedException { 
  87.     if (count_ == 0) return new RBTree(screener_, cmp_);
  88.     else return new RBTree(screener_, cmp_, tree_.copyTree(), count_);
  89.   }
  90.  
  91.  
  92.  
  93. // Collection methods  
  94.         
  95. /**
  96.  * Implements collections.Collection.includes.
  97.  * Time complexity: O(log n).
  98.  * @see collections.Collection#includes
  99. **/
  100.   public synchronized boolean includes(Object element) {
  101.     if (element == null || count_ == 0) return false;
  102.     return tree_.find(element, cmp_) != null;
  103.   }
  104.  
  105. /**
  106.  * Implements collections.Collection.occurrencesOf.
  107.  * Time complexity: O(log n).
  108.  * @see collections.Collection#occurrencesOf
  109. **/
  110.   public synchronized int occurrencesOf(Object element) {
  111.     if (element == null || count_ == 0) return 0;
  112.     return tree_.count(element, cmp_);
  113.   }
  114.  
  115. /**
  116.  * Implements collections.Collection.elements.
  117.  * Time complexity: O(1).
  118.  * @see collections.Collection#elements
  119. **/
  120.   public synchronized CollectionEnumeration elements() { 
  121.     return new RBCellEnumeration(this, tree_);
  122.   }
  123.  
  124. // ElementSortedCollection methods
  125.  
  126.  
  127. /**
  128.  * Implements collections.ElementSortedCollection.elementComparator
  129.  * Time complexity: O(1).
  130.  * @see collections.ElementSortedCollection#elementComparator
  131. **/
  132.   public synchronized Comparator elementComparator() { return cmp_; }
  133.   
  134. /**
  135.  * Reset the comparator. Will cause a reorganization of the tree.
  136.  * Time complexity: O(n log n).
  137. **/
  138.   public synchronized void elementComparator(Comparator cmp) {
  139.     if (cmp != cmp_) {
  140.       if (cmp != null) cmp = cmp;
  141.       else cmp_ = new DefaultComparator();
  142.       if (count_ != 0) {       // must rebuild tree!
  143.         incVersion();
  144.         RBCell t = tree_.leftmost();
  145.         tree_ = null;
  146.         count_ = 0;
  147.         while (t != null) {
  148.           add_(t.element(), false);
  149.           t = t.successor();
  150.         }
  151.       }
  152.     }
  153.   }
  154.  
  155.  
  156. // UpdatableCollection methods
  157.  
  158. /**
  159.  * Implements collections.UpdatableCollection.clear.
  160.  * Time complexity: O(1).
  161.  * @see collections.UpdatableCollection#clear
  162. **/
  163.   public synchronized void clear() { 
  164.     setCount(0);
  165.     tree_ = null;
  166.   }
  167.  
  168. /**
  169.  * Implements collections.UpdatableCollection.exclude.
  170.  * Time complexity: O(log n * occurrencesOf(element)).
  171.  * @see collections.UpdatableCollection#exclude
  172. **/
  173.   public synchronized void exclude(Object element) {
  174.     remove_(element, true);
  175.   }
  176.  
  177.  
  178. /**
  179.  * Implements collections.UpdatableCollection.removeOneOf.
  180.  * Time complexity: O(log n).
  181.  * @see collections.UpdatableCollection#removeOneOf
  182. **/
  183.   public synchronized void removeOneOf(Object element) {
  184.     remove_(element, false);
  185.   }
  186.  
  187. /**
  188.  * Implements collections.UpdatableCollection.replaceOneOf
  189.  * Time complexity: O(log n).
  190.  * @see collections.UpdatableCollection#replaceOneOf
  191. **/
  192.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  
  193.   throws IllegalElementException { 
  194.     replace_(oldElement, newElement, false);
  195.   }
  196.  
  197. /**
  198.  * Implements collections.UpdatableCollection.replaceAllOf.
  199.  * Time complexity: O(log n * occurrencesOf(oldElement)).
  200.  * @see collections.UpdatableCollection#replaceAllOf
  201. **/
  202.   public synchronized void replaceAllOf(Object oldElement, 
  203.                                                  Object newElement) 
  204.   throws IllegalElementException {
  205.     replace_(oldElement, newElement, true);
  206.   }
  207.  
  208. /**
  209.  * Implements collections.UpdatableCollection.take.
  210.  * Time complexity: O(log n).
  211.  * Takes the least element.
  212.  * @see collections.UpdatableCollection#take
  213. **/
  214.   public synchronized Object take() 
  215.   throws NoSuchElementException {
  216.     if (count_ != 0) {
  217.       RBCell p = tree_.leftmost();
  218.       Object v = p.element();
  219.       tree_ = p.delete(tree_);
  220.       decCount();
  221.       return v;
  222.     }
  223.     checkIndex(0);
  224.     return null; // not reached
  225.   }
  226.  
  227.  
  228. // UpdatableBag methods
  229.  
  230. /**
  231.  * Implements collections.UpdatableBag.addIfAbsent
  232.  * Time complexity: O(log n).
  233.  * @see collections.UpdatableBag#addIfAbsent
  234. **/
  235.   public synchronized void addIfAbsent(Object element) 
  236.   throws IllegalElementException {
  237.     add_(element, true);
  238.   }
  239.  
  240.  
  241. /**
  242.  * Implements collections.UpdatableBag.add.
  243.  * Time complexity: O(log n).
  244.  * @see collections.UpdatableBag#add
  245. **/
  246.   public synchronized void add(Object element) 
  247.   throws IllegalElementException {
  248.     add_(element, false);
  249.   }
  250.  
  251.  
  252. // helper methods
  253.  
  254.   private void add_(Object element, boolean checkOccurrence) 
  255.   throws IllegalElementException {
  256.     checkElement(element);
  257.     if (tree_ == null) {
  258.       tree_ = new RBCell(element);
  259.       incCount();
  260.     }
  261.     else {
  262.       RBCell t = tree_;
  263.       for (;;) {
  264.         int diff = cmp_.compare(element, t.element());
  265.         if (diff == 0 && checkOccurrence) return;
  266.         else if (diff <= 0) {
  267.           if (t.left() != null) 
  268.             t = t.left();
  269.           else {
  270.             tree_ = t.insertLeft(new RBCell(element), tree_);
  271.             incCount();
  272.             return;
  273.           }
  274.         }
  275.         else {
  276.           if (t.right() != null) 
  277.             t = t.right();
  278.           else {
  279.             tree_ = t.insertRight(new RBCell(element), tree_);
  280.             incCount();
  281.             return;
  282.           }
  283.         }
  284.       }
  285.     }
  286.   }
  287.  
  288.  
  289.   private void remove_(Object element, boolean allOccurrences) {
  290.     if (element == null) return;
  291.     while (count_ > 0) {
  292.       RBCell p = tree_.find(element, cmp_);
  293.       if (p != null) {
  294.         tree_ = p.delete(tree_);
  295.         decCount();
  296.         if (!allOccurrences) return;
  297.       }
  298.       else break;
  299.     }
  300.   }
  301.  
  302.   private void replace_(Object oldElement, Object newElement, boolean allOccurrences) 
  303.   throws IllegalElementException {
  304.     if (oldElement == null || count_ == 0 || oldElement.equals(newElement)) 
  305.       return;
  306.     while (includes(oldElement)) {
  307.       removeOneOf(oldElement);
  308.       add(newElement);
  309.       if (!allOccurrences) return;
  310.     }
  311.   }
  312.  
  313. // ImplementationCheckable methods
  314.  
  315. /**
  316.  * Implements collections.ImplementationCheckable.checkImplementation.
  317.  * @see collections.ImplementationCheckable#checkImplementation
  318. **/
  319.   public void checkImplementation() 
  320.   throws ImplementationError {
  321.  
  322.     super.checkImplementation();
  323.     assert(cmp_ != null);
  324.     assert(((count_ == 0) == (tree_ == null)));
  325.     assert((tree_ == null || tree_.size() == count_));
  326.     if (tree_ != null) {
  327.       tree_.checkImplementation();
  328.       Object last = null;
  329.       RBCell t = tree_.leftmost();
  330.       while (t != null) {
  331.         Object v = t.element();
  332.         if (last != null) 
  333.           assert(cmp_.compare(last, v) <= 0);
  334.         last = v;
  335.         t = t.successor();
  336.       }
  337.     }
  338.   }
  339.  
  340. }
  341.  
  342.